package com.ujs.code.binarysearch;

/**
 * 1.代码随想录 二分查找
 *
 * @author zhangshihao
 * @create 2023-09-10 13:03
 */
public class Search {
    public static void main(String[] args) {
        Search search = new Search();
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 6;

        int result = search.search(nums, target);
        int index = search.searchAndInsertIndex(nums, target);
        int leftIndex = search.getLeftBorder(nums, target);
        int rightIndex = search.getRightBorder(nums, target);
        // if (leftIndex == -2 || rightIndex == -2) System.out.println("{-1, -1}");
        // if (rightIndex - leftIndex > 1) System.out.println((leftIndex + 1) + "," + (rightIndex - 1));
        // System.out.println("{-1, -1}");

        int i = search.mySqrt(2147395599);
        System.out.println(i);
    }

    /**
     * 二分查找第一种实现方式。
     * 第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
     *
     * @param nums
     * @param target
     * @return
     */
    // public int search(int[] nums, int target) {
    //     int left = 0;
    //     int right = nums.length - 1;
    //     int middle = (nums.length - left) / 2;
    //     while (right >= left) {
    //         if (nums[middle] > target) {
    //             right = middle - 1;
    //         } else if (nums[middle] < target) {
    //             left = middle + 1;
    //         } else {
    //             return middle;
    //         }
    //         middle = left + (right - left) / 2;
    //     }
    //     return -1;
    // }
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int middle = left + (right + left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }


    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchAndInsertIndex(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int middle = (nums.length - left) / 2;
        while (right >= left) {
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
            middle = left + (right - left) / 2;
        }
        return right + 1;
    }

    public int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    public int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] >= target) {
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }

    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        int result = 1;
        for (int i = 0; i <= 15; i++) {
            result *= 2;
        }
        long[] nums = new long[result];
        for (int i = 0; i < result; i++) {
            nums[i] = i;
        }
        // 二分查找
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] * nums[middle] > x) {
                right = middle - 1;
            } else if (nums[middle] * nums[middle] < x) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return right;
    }

    public boolean isPerfectSquare(int x) {
        if (x == 0 || x == 1) {
            return true;
        }
        int result = 1;
        for (int i = 0; i <= 15; i++) {
            result *= 2;
        }
        long[] nums = new long[result];
        for (int i = 0; i < result; i++) {
            nums[i] = i;
        }
        // 二分查找
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] * nums[middle] > x) {
                right = middle - 1;
            } else if (nums[middle] * nums[middle] < x) {
                left = middle + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
